package _69Sqrt_x;

public class CSolution {

  public static void main(String[] args) {
    System.out.println("aa");
    System.out.println(solution(8));
    System.out.println(solution(2));
    System.out.println(solution(1));
    System.out.println(solution(0));
    System.out.println(solution(72));
    System.out.println(solution(81));
  }

  private static int solution(int x) {
    int middle;
    int low = 0;
    int high = x;
    while (low<high) {
        middle = (low+high)/2;
        if(Math.pow(middle,2)==x) {
            return middle;
        }
        if(Math.pow(middle+1,2)==x) {
            return middle+1;
        }
        if(Math.pow(middle,2)<x && Math.pow(middle+1,2)>x) {
            return middle;
        }
        if(Math.pow(middle,2)>x) {
            high = middle;
        }
        if(Math.pow(middle+1,2)<x) {
            low = middle+1;
        }
    }
    return 0;
  }
}
